home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / ctlib100.zip / INSTALL.LZH / CTBPTREE.INT < prev    next >
Text File  |  1996-10-12  |  6KB  |  146 lines
  1. {**************************************************************************}
  2. {*  BitSoft Development, L.L.C.                                           *}
  3. {*  Copyright (C) 1995, 1996 BitSoft Development, L.L.C.                  *}
  4. {*  All rights reserved.                                                  *}
  5. {*  B+ Trees Unit                                                         *}
  6. {*  Version 1.0.4                                                         *}
  7. {**************************************************************************}
  8.  
  9. unit ctBpTree;
  10.  
  11. {$X+}
  12.  
  13. interface
  14.  
  15. uses Objects,
  16.      {$ifdef ver60} BsdVer60, {$endif}
  17.      Containr, ctBTrees, ctTrees;
  18.  
  19. type
  20.   PLinkedBlock = ^TLinkedBlock;
  21.   TLinkedBlock = object(TObject)
  22.       ID : LongInt;
  23.       NextBlock : LongInt;
  24.       PrevBlock : LongInt;
  25.       Owner : Pointer;
  26.       Count : Word;
  27.       Data : PChar;
  28.       Modified : Boolean;
  29.     constructor Init (AOwner : Pointer);
  30.     destructor Done; virtual;
  31.     function At (Index : Word) : Pointer; virtual;
  32.     procedure AtCopyBlock(Index, SourceIndex : Word; SourceBlock :
  33.       PLinkedBlock; ItemCount : Word);
  34.     procedure AtDelete(Index: Word);
  35.     procedure AtDeleteBlock(Index, ItemCount : Word);
  36.     procedure AtInsert(Index : Word; Item : Pointer);
  37.     procedure AtPut (Index : Word; Item : Pointer); virtual;
  38.     procedure FreeAll; virtual;
  39.     procedure Insert (Item : Pointer);
  40.     function IsFull : Boolean;
  41.     function LoadData (AOffset : LongInt): Boolean; virtual;
  42.     function Search (Key : Pointer; var Index : Word) : Boolean; virtual;
  43.     function StoreData: Boolean; virtual;
  44.   end; { TLinkedBlock }
  45.  
  46. type
  47.   PmWayKeyNode = ^TmWayKeyNode;
  48.   TmWayKeyNode = object (TmWayNode)
  49.     function GetKey(Item : Pointer) : Pointer; virtual;
  50.   end; { TmWayKeyNode }
  51.  
  52. const
  53.   TBPlusTreeSig : array [0..10] of Char = 'ctBPlusTree';
  54.  
  55. const
  56.   TBPlusTreeVer = $0100;
  57.  
  58. type
  59.   PBPlusTree = ^TBPlusTree;
  60.   TBPlusTree = object(TBaseBTree)
  61.     constructor Init (ADegree, ABlockSize, ADataSize, AKeySize : Word;
  62.       AStream : PStream; IndexBufferSize, DataBufferSize : LongInt);
  63.     constructor Open (AStream : PStream; IndexBufferSize,
  64.       DataBufferSize : LongInt);
  65.     destructor Done; virtual;
  66.     function Delete (Item : Pointer) : Boolean; virtual;
  67.     function DeleteAll : Boolean; virtual;
  68.     function DeleteAllThat (Test: Pointer): Boolean;  virtual;
  69.     function Find (Key : Pointer; var Hits : LongInt) : Boolean;
  70.       virtual;
  71.     function FindThat (Key, Test : Pointer; var Hits : LongInt) :
  72.       Boolean; virtual;
  73.     function First : Pointer; virtual;
  74.     function FirstThat (Test : Pointer) : Pointer; virtual;
  75.     procedure Flush; virtual;
  76.     function FreeAll : Boolean; virtual;
  77.     function FreeAllThat (Test: Pointer): Boolean; virtual;
  78.     function ForEach (Action: Pointer): Boolean; virtual;
  79.     function ForEachThat (Test, Action : Pointer): Boolean; virtual;
  80.     function Height : Word; virtual;
  81.     function Insert (Item : Pointer) : Boolean; virtual;
  82.     function ItemReplace (OldItem, NewItem : Pointer) : Boolean; virtual;
  83.     function KeyFirst (Key : Pointer) : Pointer; virtual;
  84.     function KeyLast (Key : Pointer) : Pointer; virtual;
  85.     function Last : Pointer; virtual;
  86.     function LastThat(Test : Pointer) : Pointer; virtual;
  87.     function Next (Item : Pointer) : Pointer; virtual;
  88.     function NextThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
  89.     function NewBlock : PLinkedBlock; virtual;
  90.     function NewNode : PmWayNode; virtual;
  91.     function Prev (Item : Pointer) : Pointer; virtual;
  92.     function PrevThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
  93.   private
  94.       BlockSize : Word;
  95.       BlockDataSize : Word;
  96.       CurrentBlock : PLinkedBlock;
  97.       FirstBlock : LongInt;
  98.       BlockBuffer : PCollection;
  99.       BlockBufferSize : LongInt;
  100.       FreeBlocks : LongInt;
  101.     function BlockStoredSize : Word; virtual;
  102.     function ConcatenateBlock : Boolean;
  103.     procedure GetBlock (ID : LongInt);
  104.     function GetNewBlock : PLinkedBlock;
  105.     function InitTree (ABlockBufferSize : LongInt): Boolean;
  106.     function LocateFirst (Key : Pointer; var Index : Word) : Boolean;
  107.     function LocateItem (Item : Pointer; var Index : Word) : Boolean;
  108.     function LocateLast (Key : Pointer; var Index : Word) : Boolean;
  109.     procedure ReadHeader; virtual;
  110.     function RedistributeBlockEmpty (var NewKey : Pointer) : Boolean;
  111.     function RedistributeBlockFull (Item : Pointer; Index : Word;
  112.       var NewKey : Pointer) : Boolean;
  113.     procedure ReleaseBlock (Block : PLinkedBlock);
  114.     function SplitBlock (Item : Pointer; Index : Word; var NewKey : Pointer;
  115.       var ChildNode : LongInt) : Boolean;
  116.     function ValidSignature (ASignature : PChar) : Boolean;
  117.     function ValidVersion (AVersion : Word) : Boolean;
  118.     procedure WriteHeader; virtual;
  119.   end; { TBPlusTree }
  120.  
  121. type
  122.   PObjectBPlusTree = ^TObjectBPlusTree;
  123.   TObjectBPlusTree = object(TBPlusTree)
  124.     constructor Init (ADegree, ABlockSize, ADataSize, AKeySize : Word;
  125.       AStream : PStream; IndexBufferSize, DataBufferSize : LongInt);
  126.     procedure FreeItem (Item : Pointer); virtual;
  127.     function GetItem (var S : TStream) : Pointer; virtual;
  128.     function NewBlock : PLinkedBlock; virtual;
  129.     procedure PutItem (var S : TStream; Item : Pointer); virtual;
  130.   private
  131.     function BlockStoredSize : Word; virtual;
  132.   end; { TObjectBPlusTree }
  133.  
  134. type
  135.   PLinkedObjectBlock = ^TLinkedObjectBlock;
  136.   TLinkedObjectBlock = object(TLinkedBlock)
  137.     function At (Index : Word) : Pointer; virtual;
  138.     procedure AtPut (Index : Word; Item : Pointer); virtual;
  139.     procedure FreeAll; virtual;
  140.     function LoadData (AOffset : LongInt): Boolean; virtual;
  141.     function StoreData: Boolean; virtual;
  142.   end; { TLinkedObjectBlock }
  143.  
  144. implementation
  145. end.
  146.